home *** CD-ROM | disk | FTP | other *** search
/ MacHack 2001 / MacHack 2001.toast / pc / The Hacks / SpellCompositor / Sorter.java < prev    next >
Encoding:
Text File  |  2001-06-23  |  9.3 KB  |  250 lines
  1. // For use with Arcana Spell Manager, prog.: S.C. Ziegler
  2.  
  3. //    Syntactically Correct on 06.24.00
  4.  
  5. // This example is derived  examples in _Java Examples in a Nutshell_. 
  6. // (http://www.oreilly.com)
  7. // Copyright (c) 1997 by David Flanagan
  8.  
  9. package Arcana;
  10.  
  11. // These are some classes we need for internationalized string sorting
  12. import java.text.Collator; 
  13. import java.text.CollationKey;
  14. import java.util.Locale;
  15.  
  16. /**
  17.  * This class defines a bunch of static methods for efficiently sorting
  18.  * arrays of Strings or other objects.  It also defines two interfaces that
  19.  * provide two different ways of comparing objects to be sorted.
  20.  **/
  21. public class Sorter {
  22.   /**
  23.    * This interface defines the compare() method used to compare two objects.
  24.    * To sort objects of a given type, you must provide an appropriate Comparer
  25.    * object with a compare() method that orders those objects as desired
  26.    **/
  27.   public static interface Comparer {
  28.     /**
  29.      * Compare objects and return a value that indicates their relative order:
  30.      * if (a > b) return > 0; 
  31.      * if (a == b) return 0;
  32.      * if (a < b) return < 0. 
  33.      **/
  34.     public int compare(Object a, Object b);
  35.   }
  36.  
  37.   /**
  38.    * This is an alternative interface that can be used to order objects.  If a
  39.    * class implements this Comparable interface, then any two instances of that
  40.    * class can be directly compared by invoking the compareTo() method.
  41.    **/
  42.   public static interface Comparable {
  43.     /** 
  44.      * Compare objects and return a value that indicates their relative order:
  45.      * if (this > other) return > 0
  46.      * if (this == other) return 0
  47.      * if (this < other) return < 0
  48.      **/
  49.     public int compareTo(Object other);
  50.   }
  51.  
  52.   /**
  53.    * This is an internal Comparer object (created with an anonymous class)
  54.    * that compares two ASCII strings.  
  55.    * It is used in the sortAscii methods below.
  56.    **/
  57.   private static Comparer ascii_comparer = new Comparer() {
  58.     public int compare(Object a, Object b) {
  59.       return ((String)a).compareTo((String)b);
  60.     }
  61.   };
  62.  
  63.   /**
  64.    * This is another internal Comparer object.  It is used to compare two
  65.    * Comparable objects.  It is used by the sort() methods below that take
  66.    * Comparable objects as arguments instead of arbitrary objects
  67.    */
  68.   private static Comparer comparable_comparer = new Comparer() {
  69.     public int compare(Object a, Object b) {
  70.       return ((Comparable)a).compareTo(b);
  71.     }
  72.   };
  73.  
  74.   /** Sort an array of ASCII strings into ascending order */
  75.   public static void sortAscii(String[] a) {
  76.     // Note use of the ascii_comparer object
  77.     sort(a, null, 0, a.length-1, true, ascii_comparer); 
  78.   }
  79.  
  80.   /** 
  81.    * Sort a portion of an array of ASCII strings into ascending or descending
  82.    * order, depending on the argument up
  83.    **/
  84.   public static void sortAscii(String[] a, int from, int to, boolean up) {
  85.     // Note use of the ascii_comparer object
  86.     sort(a, null, from, to, up, ascii_comparer);
  87.   }
  88.  
  89.   /** Sort an array of ASCII strings into ascending order, ignoring case */
  90.   public static void sortAsciiIgnoreCase(String[] a) {
  91.     sortAsciiIgnoreCase(a, 0, a.length-1, true);
  92.   }
  93.  
  94.   /**
  95.    * Sort an portion of an array of ASCII strings, ignoring case.  Sort into
  96.    * ascending order if up is true, otherwise sort into descending order.
  97.    **/
  98.   public static void sortAsciiIgnoreCase(String[] a, int from, int to,
  99.                                          boolean up) {
  100.     if ((a == null) || (a.length < 2)) return;
  101.     // Create a secondary array of strings that contains lowercase versions
  102.     // of all the specified strings. 
  103.     String b[] = new String[a.length];
  104.     for(int i = 0; i < a.length; i++) b[i] = a[i].toLowerCase();
  105.     // Sort that secondary array, and rearrange the original array 
  106.     // in exactly the same way, resulting in a case-insensitive sort.
  107.     // Note the use of the ascii_comparer object
  108.     sort(b, a, from, to, up, ascii_comparer);
  109.   }
  110.  
  111.   /** 
  112.    * Sort an array of strings into ascending order, using the correct
  113.    * collation order for the default locale
  114.    **/
  115.   public static void sort(String[] a) {
  116.     sort(a, 0, a.length-1, true, false, null);
  117.   }
  118.  
  119.   /**
  120.    * Sort a portion of an array of strings, using the collation order of
  121.    * the default locale.   If up is true, sort ascending, otherwise, sort
  122.    * descending.  If ignorecase is true, ignore the capitalization of letters
  123.    **/
  124.   public static void sort(String[] a, int from, int to, 
  125.                           boolean up, boolean ignorecase) {
  126.     sort(a, from, to, up, ignorecase, null);
  127.   }
  128.  
  129.   /**
  130.    * Sort a portion of an array of strings, using the collation order of
  131.    * the specified locale.   If up is true, sort ascending, otherwise, sort
  132.    * descending.  If ignorecase is true, ignore the capitalization of letters
  133.    **/
  134.   public static void sort(String[] a, int from, int to, 
  135.                           boolean up, boolean ignorecase, 
  136.                           Locale locale) {
  137.     // Don't sort if we don't have to
  138.     if ((a == null) || (a.length < 2)) return;
  139.  
  140.     // The java.text.Collator object does internationalized string compares
  141.     // Create one for the specified, or the default locale.
  142.     Collator c;
  143.     if (locale == null) c = Collator.getInstance();
  144.     else c = Collator.getInstance(locale);
  145.  
  146.     // Specify whether or not case should be taken into account in the sort.
  147.     // Note: this option does not seem to work correctly in JDK 1.1.1
  148.     // using the default American English locale.
  149.     if (ignorecase) c.setStrength(Collator.SECONDARY);
  150.  
  151.     // Use the Collator object to create an array of CollationKey objects that
  152.     // correspond to each of the strings.  
  153.     // Comparing CollationKeys is much quicker than comparing Strings
  154.     CollationKey[] b = new CollationKey[a.length];
  155.     for(int i = 0; i < a.length; i++) b[i] = c.getCollationKey(a[i]);
  156.  
  157.     // Now define a Comparer object to compare collation keys, using an
  158.     // anonymous class.
  159.     Comparer comp =  new Comparer() {
  160.       public int compare(Object a, Object b) {
  161.         return ((CollationKey)a).compareTo((CollationKey)b);
  162.       }
  163.     };
  164.  
  165.     // Finally, sort the array of CollationKey objects, rearranging the 
  166.     // original array of strings in exactly the same way.
  167.     sort(b, a, from, to, up, comp);
  168.   }
  169.  
  170.   /** Sort an array of Comparable objects into ascending order */
  171.   public static void sort(Comparable[] a) {
  172.     sort(a, null, 0, a.length-1, true);
  173.   }
  174.  
  175.   /**
  176.    * Sort a portion of an array of Comparable objects.  If up is true,
  177.    * sort into ascending order, otherwise sort into descending order.
  178.    **/
  179.   public static void sort(Comparable[] a, int from, int to, boolean up) {
  180.     sort(a, null, from, to, up, comparable_comparer);
  181.   }
  182.  
  183.   /**
  184.    * Sort a portion of array a of Comparable objects.  If up is true,
  185.    * sort into ascending order, otherwise sort into descending order.
  186.    * Re-arrange the array b in exactly the same way as a.
  187.    **/
  188.   public static void sort(Comparable[] a, Object[] b, 
  189.                           int from, int to, boolean up) {
  190.     sort(a, b, from, to, up, comparable_comparer);
  191.   }
  192.  
  193.   /**
  194.    * Sort an array of arbitrary objects into ascending order, using the 
  195.    * comparison defined by the Comparer object c
  196.    **/
  197.   public static void sort(Object[] a, Comparer c) {
  198.     sort(a, null, 0, a.length-1, true, c);
  199.   }
  200.  
  201.   /**
  202.    * Sort a portion of an array of objects, using the comparison defined by
  203.    * the Comparer object c.  If up is true, sort into ascending order, 
  204.    * otherwise sort into descending order.
  205.    **/
  206.   public static void sort(Object[] a, int from,int to, boolean up, Comparer c){
  207.     sort(a, null, from, to, up, c);
  208.   }
  209.   
  210.   /**
  211.    * This is the main sort() routine.  It performs a quicksort on the elements
  212.    * of array a between the element from and the element to.  The up argument
  213.    * specifies whether the elements should be sorted into ascending (true) or
  214.    * descending (false) order.  The Comparer argument c is used to perform
  215.    * comparisons between elements of the array.  The elements of the array b
  216.    * are reordered in exactly the same way as the elements of array a are.
  217.    **/
  218.   public static void sort(Object[] a, Object[] b, 
  219.                           int from, int to, 
  220.                           boolean up, Comparer c)
  221.   {
  222.     // If there is nothing to sort, return
  223.     if ((a == null) || (a.length < 2)) return;
  224.  
  225.     // This is the basic quicksort algorithm, stripped of frills that can make
  226.     // it faster but even more confusing than it already is.  You should
  227.     // understand what the code does, but don't have to understand just 
  228.     // why it is guaranteed to sort the array...
  229.     // Note the use of the compare() method of the Comparer object.
  230.     int i = from, j = to;
  231.     Object center = a[(from + to) / 2];
  232.     do {
  233.       if (up) {  // an ascending sort
  234.         while((i < to) && (c.compare(center, a[i]) > 0)) i++;
  235.         while((j > from) && (c.compare(center, a[j]) < 0)) j--;
  236.       } else {   // a descending sort
  237.         while((i < to) && (c.compare(center, a[i]) < 0)) i++;
  238.         while((j > from) && (c.compare(center, a[j]) > 0)) j--;
  239.       } 
  240.       if (i < j) { 
  241.         Object tmp = a[i];  a[i] = a[j];  a[j] = tmp;          // swap elements
  242.         if (b != null) { tmp = b[i]; b[i] = b[j]; b[j] = tmp; }// swap b, too
  243.       }
  244.       if (i <= j) { i++; j--; }
  245.     } while(i <= j);
  246.     if (from < j) sort(a, b, from, j, up, c); // recursively sort the rest
  247.     if (i < to) sort(a, b, i, to, up, c);
  248.   }
  249. }
  250.